package com.lw.leetcode.tree.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 面试题 17.17. 多次搜索
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/14 13:31
 */
public class MultiSearch {

    public static void main(String[] args) {
        MultiSearch test = new MultiSearch();
        // [[1,4],[8],[],[3],[1,4,7,10],[5]]
        String big = "mississippi";
        String[] smalls = {"is", "ppi", "hi", "sis", "i", "ssippi"};

        int[][] ints = test.multiSearch(big, smalls);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }

    private List<List<Integer>> lists;
    private Map<String, Integer> map;

    public int[][] multiSearch(String big, String[] smalls) {
        int length = smalls.length;
        map = new HashMap<>();
        lists = new ArrayList<>(length);
        Node root = new Node();
        for (int i = 0; i < length; i++) {
            String small = smalls[i];
            map.put(small, i);
            lists.add(new ArrayList<>());
            add(root, small, 0);
        }
        char[] arr = big.toCharArray();
        int l = big.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < l; i++) {
            sb.setLength(0);
            find(arr, i, root, sb, i);
        }
        int[][] values = new int[length][];
        for (int i = 0; i < length; i++) {
            List<Integer> list = lists.get(i);
            values[i] = lst2Arr(list);
        }
        return values;
    }

    private void find(char[] arr, int index, Node node, StringBuilder sb, int st) {
        if (arr.length == index) {
            return;
        }
        int i = arr[index] - 'a';
        Node no = node.arr[i];
        if (no == null) {
            return;
        }
        sb.append(arr[index]);
        if (no.end) {
            lists.get(map.get(sb.toString())).add(st);
        }
        find(arr, index + 1, no, sb, st);
    }

    private void add(Node node, String str, int index) {
        if (str.length() == index) {
            node.end = true;
            return;
        }
        int i = str.charAt(index) - 'a';
        Node no = node.arr[i];
        if (no == null) {
            no = new Node();
            node.arr[i] = no;
        }
        add(no, str, index + 1);
    }

    private int[] lst2Arr(List<Integer> lst) {
        int size = lst.size();
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = lst.get(i);
        }
        return res;
    }

    private static class Node {
        private Node[] arr = new Node[26];
        private boolean end = false;
    }

}
